The media access control (MAC) layer's primary function is to provide a fair mechanism to control access of shared communication media. However, in a wireless communication media such as IEEE 802.11 WLAN, prior to transmitting a frame, the MAC layer must gain access to the network, which it does through two different access mechanisms: a contention-based mechanism, called the distributed coordination function (DCF) and a centrally controlled access mechanism, called the point coordination function (PCF).
The PCF modes allow the implementation of a quality of service (QoS) mechanism, but it is optional and requires extra interactions in order to negotiate a QoS between the mobile terminal and the access point (AP). The DCF mode, considered as the default mode, does not provide any QoS mechanism. Consequently all stations including the base station AP in a wireless local area network (WLAN) have the same probability of acquiring access to the medium and sending data via the medium. This type of service is referred to as a “best effort”.
Three inter-frame space (IFS) intervals defer an IEEE 802.11 station's access to the medium and provide various levels of priority. Each interval defines the duration between the end of the last symbol of the previous frame to the beginning of the first symbol of the next frame. The Short Interframe Space (SIPS) provides the highest priority level by allowing some frames to access the medium before others, such as an ACK frame, a Clear-to-Send (CTS) frame, or a fragment of a previous data frame.
Simultaneous transmit attempts from a number of wireless stations lead to collisions in both the downlink and the uplink communication media, since only one transport stream can be transmitted during any one period. The problem is particularly acute during periods of high traffic loads and may render the protocol unstable. The IEEE 802.11 MAC layer uses collision avoidance rather than collision detection in order to simultaneously transmit and receive data. To resolve collisions, subsequent transmission attempts are typically staggered randomly in time using a binary exponential backoff. The DCF uses physical and virtual carrier sense mechanisms (carrier sense multiple access with collision avoidance (CSMA/CA)) with a binary exponential backoff that allows access attempts after sensing the channel for activity.
The backoff procedure for the family of IEEE 802.11 standards was first introduced for the DCF mode as the basic solution for collision avoidance, and further employed by the IEEE 802.11e to solve the problem of internal collisions between enhanced distributed channel access functions (EDCAFs). In the emerging IEEE 802.11n standard, the backoff procedure is still used as the fundamental approach for supporting distributed access among mobile stations. Currently, almost all commercially available wireless products of the IEEE 802.11 series use DCF/EDCAF as the solution for medium access and thus heavily depend on the backoff mechanism to avoid collisions. As used herein, “/” denotes alternative names for the same or similar components or structures. That is, a “/” can be taken as meaning “or” as used herein.
The principle and operations of the exponential random backoff procedure are similar in both standards. In order to set the background for the present invention, the backoff procedure specified in IEEE 802.11 is described. Before transmitting each frame, a mobile station (including access point (AP)) determines the state of the wireless medium by physical or virtual carrier sensing, and if busy, the station chooses a random integer uniformly distributed between 0 and the contention window (CW) as the initial value of the slot count for backing off. Once the medium is determined to be idle after a DCF inter-frame space (DIFS) plus the random number of slot count, where the mobile station decreases the slot count by one for each slot time, then the mobile station can transmit. This procedure is suspended if the medium is determined to be busy at any time during backing off. The contention window (CW) increases exponentially upon each unsuccessful transmission attempt. It begins with a minimum value CWmin and increases up to a maximum value CWmax. All parameters related to the backoff procedure, including the slot time, DIFS, CWmin and CWmax, are specified for the physical layer.
FIG. 1 is an exemplary representation of the random backoff procedure described above. A wireless local area network (WLAN) with one access point and three associated mobile stations is considered in this scenario. As used herein, an access point includes bridges, routers and brouters and any other device used by stations to access a network. An AP also acts as an interconnection point between a radio network (wireless network) and a wired local area network (LAN). In FIG. 1, two rounds of medium contention are shown. To start, the access point (AP) transmits a frame. When the transmission concludes, the medium becomes idle. After the medium is determined to be idle without interruption for a period of time equal to DIFS, all stations including the AP start the exponential random backoff procedure to contend for the medium. At this moment each station maintains a slot count for backing off. For the AP that wins the contention in the previous round of contention, its slot count is randomly chosen from contention window [0, CW], while other stations retain their slot count as in the previous round. The slot count is used to determine how long the station has to wait to determine if the medium is busy before it can transmit. As shown in FIG. 1, during the first round of contention, the random number used for the slot count for the AP is 7. The slot count for station 1 is 8. For station 2 the slot count is 5 and for station 3 the slot count is 3. As each time slot elapses and the medium remains idle, all stations decrease their slot count by one respectively. Since station 3 has the smallest backoff slot count (3), station 3 wins the contention after the medium is idle for a period of 3 time slots and station 3 initiates a new frame transmission at the 4th time slot. Note that as of the time station 3 transmits, other stations have decreased their slot count by three. When station 3 completes its transmission, the second round of contention begins and station 3 randomly chooses a value 8 from contention window [0, CW] as its slot count. As in the first round, other stations use their remaining slot count for backing off. Now, the AP has a slot count of 4. Station 1 has a slot count of 5. Station 2 has a slot count of 2 and station 3 has a slot count of 8. In this round of contention, station 2 has the shortest slot count so it wins and transmits a frame after the DIFS period plus two slot times. This procedure repeats throughout the lifetime of the network.
A major deficiency of the random backoff procedure lies in that, the randomly chosen value of the slot count may degenerate the utility of the medium and thus degrade the performance of carrier sense multiple access (CSMA) technique. Two factors may cause the degeneration. First, as specified in the standard, the station with the smallest backoff time (slot count) is the winner to access the medium, thus a period when the medium is idle exists before next transmission. The existence of such a vacancy between successive frame transactions negatively influences the efficiency of the backoff procedure. The second factor is the possibility of collisions among multiple stations. Though it is greatly relieved by the adoption of randomization during selection of the backoff slots, its negative impact on the network performance can still not be neglected, particularly when the number of contending stations is large.
Another deficiency of the random backoff procedure is the lack of fairness among the stations. The method that doubles the contention window upon unsuccessful transmission may put a station at a disadvantage during the next contention interval/period, as it inclines to choose a slot count larger than its counterparts. Such a binary exponentially doubled backoff procedure severely defers access to the medium, and may lead to the bandwidth starvation in some cases. Experience has shown that the difference of throughput of stations within the same network may reach 30% of the average.
Many backoff schemes have been proposed to overcome these issues. In one prior art backoff scheme, a multiplicative increase and linear decrease (MILD) algorithm was introduced to change the backoff contention window in a moderate way, and thus improve the fairness. In another prior at scheme, to achieve increased fairness among stations, the contention window is changed dynamically with the estimated fair share of channel assigned to each station. In yet another prior art scheme, a general mechanism is presented for translating a given fairness model into a corresponding contention resolution scheme. A backoff algorithm that achieves proportional fairness is derived using the contention resolution scheme. In yet another prior at scheme, the probability distribution of slot selection is considered, and an exponential random walking backoff algorithm is proposed in which the backoff slot count decrements with a predetermined probability. In yet another media access scheme, time slots are assigned to each station, where the number of time slots is at least as great as the number of stations in the network. This scheme essentially replaces a contention-based frequency division scheme, such as CSMA, by a time division multiple access scheme where time slots are assigned to each station. A great deal of research has been done in the area of backoff algorithms, fairness and quality of service remain largely unresolved.
Thus, it would be advantageous to have a solution to the fairness and quality of service issues of the random backoff procedures specified by the IEEE 802.11 standards.